#pragma once

// #include <iostream>
// 
// char solve( std::string str ) {
//     char r;
//     size_t max = 0;
//     size_t diff;
//     for ( char c = 122; c > 96; --c )
//     {
//         if ( str.find( c ) != std::string::npos )
//         {
//             diff = str.find_last_of( c ) - str.find_first_of( c );
//             if ( diff >= max )
//             {
//                 // 				std::cout << "Switch: " << r << " -> " << c << str.find_last_of(c) - str.find_first_of(c) <<std::endl;
//                 r = c;
//                 max = diff;
//             }
//         }
//     }
//     return r;
// }

#include <string>
#include <array>
#include <limits>
#include <optional>
#include <algorithm>
struct CharData
{
    CharData(size_t pp, size_t vv, char cc) : firstPos(pp), value(vv), c(cc){}
    size_t firstPos;
    size_t value;
    char c;
    bool operator<(const CharData & other) const {
        return other.value == value ? c > other.c : value < other.value;
    }
};


char solve( const std::string & str ) {
    std::array<std::optional<CharData>, std::numeric_limits<char>::max()> data;
    for ( size_t pos = 0; pos < str.size(); pos++ )
    {
        char c = str[pos];
        auto & charData = data[static_cast<size_t>(c)];
        if( charData ){
            charData->value = pos - charData->firstPos;
        } else {
            charData.emplace(pos, 0, c);
        }
    }
    std::sort(data.begin(), data.end());
    return data.back()->c;
}
